import java.util.ArrayList;
import java.util.List;

/**
 * Created by zhourh on 2018/8/13.
 *
 * 给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。
 */
public class MinimumDistanceBetweenBSTNodes {

    public static void main(String[] args) {
        TreeNode node4 = new TreeNode(4);
        TreeNode node2 = new TreeNode(2);
        TreeNode node6 = new TreeNode(6);
        TreeNode node1 = new TreeNode(1);
        TreeNode node3 = new TreeNode(3);

        node4.left = node2;
        node4.right = node6;
        node2.left = node1;
        node2.right = node3;

        System.out.println(new MinimumDistanceBetweenBSTNodes().minDiffInBST(node4));
    }

    public int minDiffInBST(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return Integer.MAX_VALUE;
        }

        List<Integer> sortValues = sortList(root, null);

        int min = Integer.MAX_VALUE;
        for (int i = 1; i < sortValues.size(); i++) {
            min = Math.min(min, sortValues.get(i) - sortValues.get(i - 1));
        }

        return min;

    }

    private List<Integer> sortList(TreeNode node, List<Integer> ans) {
        if (ans == null) {
            ans = new ArrayList<>();
        }

        if (node.left != null) {
            sortList(node.left, ans);
        }
        ans.add(node.val);
        if (node.right != null) {
            sortList(node.right, ans);
        }

        return ans;
    }

}
